package recursive.numTrees;
/**
 * @Date 2020/04/05
 * @author 王光浩
 * @Thinking 使用动态规划
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
public class MyMethodThree {
	public int numTrees(int n) {
		int[] ret=new int[n+1];
		ret[0]=1;
		ret[1]=1;
		for(int i=2;i<=n;i++) {
			for(int j=1;j<=i;i++) {
				ret[i]+=(ret[j-1]*ret[i-j]);
			}
		}
		return ret[n];
	}
}
